package com.sunny.l41;

public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if(null == num || 0 == num.length)
            return null;
        return dfs(num, 0, num.length-1);
    }
    public TreeNode dfs(int[] num, int start, int end){
        int len = end - start + 1;
        if(1 == len){
            return new TreeNode(num[start]);
        }
        if(2 == len){
            TreeNode ret = new TreeNode(num[end]);
            ret.left = new TreeNode(num[start]);
            return ret;
        }
        int t = (start + end + 1) >> 1;
        TreeNode root = new TreeNode(num[t]);
        root.left = dfs(num, start, t-1);
        root.right = dfs(num, t+1, end);
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
